/**
 * @Author: zqb
 * @Description: //找第k小的数据，利用类快速排序
 * @Date: Created in 22:27 2020/1/22
 * @Create By:
 */
public class FindKNumOfQuickSort {


    public static void main(String[] args) {

//        int [] array=new int[]{8,9,2,1,4,6,0};
        int[] array = {89, 2, 4, 8, 9, 32, 11, 3, 21};

        System.out.println(findKNum(array, 0, array.length - 1, array.length));
        System.out.println(findKNum(array, 0, array.length - 1, 2));

    }


    public static int findKNum(int[] array, int low, int high, int k) {

        int i, j;
        i = low;
        j = high;
        int mid = array[i];
        while (i < j) {
            //逆向遍历找到小于mid的值
            while (i < j && mid <= array[j]) {
                j--;
            }
            if (i < j) {
                array[i] = array[j];//先赋值后++
                i++;
            }

            //正向向遍历找到大于mid的值
            while (i < j && mid >= array[i]) {
                i++;
            }
            if (i < j) {
                array[j] = array[i];//先赋值后++
                j--;
            }
        }

        array[i] = mid;

        //第一次在 i-low出现了问题
        if ((k - 1) == i - low) {
            return mid;
        } else if ((k - 1) < i - low) {
            return findKNum(array, low, i - 1, k);
        } else {
            return findKNum(array, i + 1, high, (k - 1) - (i - low));
        }
    }

}
